package club.vann.nowcoder;

/**
 * <p>难度：Medium</p>
 * <p>题目：矩阵中最小路径和</p>
 * <p>描述：给定一个 n * m 的矩阵 a，从左上角开始每次只能向右或者向下走，最后到达右下角的位置，路径上所有的数字累加起来就是路径和，输出所有的路径中最小的路径和。
 * 示例1
 * 输入
 * 复制
 * [[1,3,5,9],[8,1,3,4],[5,0,6,1],[8,8,4,0]]
 * 返回值
 * 复制
 * 12
 * 备注:
 * 1 \leq n,m \leq 20001≤n,m≤2000
 * 1 \leq arr_{i,j} \leq 1001≤arr
 * i,j
 * ​
 *  ≤100</p>
 * @author vann
 * @program now-coder
 * @description
 * @date 2021-04-20:15:01:37
 */
public class NC59 {
    public static void main(String[] args) {
        NC59 nc59 = new NC59();

        System.out.println("Result["+TestCase.ANS+"] : " + nc59.minPathSum1(TestCase.MATRIX));
    }

    /**
     *
     * @param matrix int整型二维数组 the matrix
     * @return int整型
     */
    public int minPathSum (int[][] matrix) {
        // write code here
        // 解法一：
        int m = matrix.length;
        int n = matrix[0].length;
        int[][] dp = new int[m][n];
        dp[0][0] = matrix[0][0];

        for(int i = 1; i < m; i ++) {
            dp[i][0] = dp[i-1][0] + matrix[i][0];
        }

        for(int i = 1; i < n; i ++) {
            dp[0][i] = dp[0][i-1] + matrix[0][i];
        }

        for(int i = 1; i < m; i ++) {
            for(int j = 1; j < n; j ++) {
                dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + matrix[i][j];
            }
        }

        return dp[m-1][n-1];
    }

    /**
     * 解法二：
     *
     * @param matrix
     * @return
     */
    public int minPathSum1 (int[][] matrix) {
        int len = matrix[0].length;
        int[] dp = new int[len];
        dp[0] = matrix[0][0];

        for(int i = 1; i < len; i ++) {
            dp[i] = dp[i-1] + matrix[0][i];
        }

        for(int j = 1; j < matrix.length; j ++) {
            dp[0] = dp[0] + matrix[j][0];
            for(int i = 1; i < len; i ++) {
                dp[i] = Math.min(dp[i-1] + matrix[j][i], dp[i] + matrix[j][i]);
            }
        }

        return dp[len-1];
    }

    static class TestCase {
        public static int ANS = 12;
        public static int[][] MATRIX = {{1,3,5,9},{8,1,3,4},{5,0,6,1},{8,8,4,0}};
    }
}